package com.cat.chapter035;

import java.util.PriorityQueue;

/**
 * @author cat
 * @description https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
 * @create 2025/6/3 10:29
 * @since JDK17
 */

public class MedianFinder {
    // 大根堆
    private static PriorityQueue<Integer> maxh;
    // 小根堆
    private static PriorityQueue<Integer> minh;
    // 大根堆放较小的那一部分，而小根堆放较大的部分

    public MedianFinder() {
        maxh = new PriorityQueue<>((a,b) -> b - a);
        minh = new PriorityQueue<>((a,b) -> a - b);
    }

    public void addNum(int num) {
        if (maxh.isEmpty() || num <= maxh.peek()) {
            maxh.add(num);
        } else {
            minh.add(num);
        }
        balance();
    }

    private void balance() {
        // 差距有两个了
        if (Math.abs(maxh.size() - minh.size()) == 2) {
            if (maxh.size() > minh.size()) {
                minh.add(maxh.poll());
            } else {
                maxh.add(minh.poll());
            }
        }
    }

    public double findMedian() {
        if (maxh.size() == minh.size()) {
            return (maxh.peek() + minh.peek()) / 2.0;
        } else if (maxh.size() > minh.size()) {
            return maxh.peek();
        } else {
            return minh.peek();
        }
    }
}
